A color image often is composed of an array of pixels, with each pixel including multiple color components. For example, in a three-color system, an electronic scanner may be used to separate a color image into red, green and blue (“RGB”) color components, with each color component represented numerically. Thus, in an 8-bit, three color system, each pixel may be represented by three color values, with each color value being a number in the range between 0 and 255. For example, the color values of a pixel in an 8-bit RGB system may be expressed as (20, 77, 201), where the numbers 20, 77 and 201 represent the values of the red, green and blue components, respectively, for that pixel.
Color output devices, such as color printers, typically produce output images using cyan, magenta, yellow, and sometimes black colorants. Accordingly, color output devices typically represent images using cyan, magenta and yellow (“CMY”) color components (i.e., a three color system), or cyan, magenta, yellow and black (“CMYK”) color components (i.e., a four-color system). To reproduce a color image on a color output device, therefore, the image data typically must be converted from one color component system (e.g., RGB) to another system (e.g., CMY). In particular, the input color values of each pixel must be converted to respective output color values to accurately reproduce the image on a print medium. For example, an input pixel having RGB values of (20, 77, 201) may correspond to an output pixel having CMY values of (100, 82, 0).
More generally, it is often desirable to convert color values from a first color system to a second color system. One known method for converting color values uses a lookup table that provides a corresponding set of second color values for each set of first color values. In an 8-bit system, each first color component may have any value between 0 and 255. Thus, in a three-color system, each pixel may be represented by any one of over 16 million different combinations of first color values (2563=16,777,216). Due to memory constraints, however, it is impractical for each of the possible combinations of first color values to be listed in the lookup table. Instead, a “sparse” lookup table is created that includes regularly spaced or intermittent combinations of first color values. For example, if a three-dimensional lookup table includes only thirty-three entries per dimension the lookup table will have 35,937 entries (333), which may be practically implemented in computer memory.
Referring to FIG. 1, each component of the first color value, for example, red, green or blue, can be visualized as corresponding to a respective axis in three dimensional space 10. A sparse lookup table can be visualized as including multiple points within three dimensional space 10. For example, point 20 may correspond to first color value (192, 168, 232), point 22 may correspond to first color value (200, 168, 232), point 24 may correspond to first color value (200, 168, 224), point 26 may correspond to first color value (192, 168, 224), point 28 may correspond to first color value (192, 160, 224), point 30 may correspond to first color value (192, 160, 232), point 32 may correspond to first color value (200, 160, 232) and point 34 may correspond to first color value (200, 160, 224).
For each point in the lookup table, there is also an associated second color value. Thus, point 20 may correspond to second color value (28, 36, 0), point 22 may correspond to second color value (25, 38, 0), point 24 may correspond to second color value (24, 37, 0), point 26 may correspond to second color value (27, 36, 0), point 28 may correspond to second color value (28, 41, 0), point 30 may correspond to second color value (29, 42, 0), point 32 may correspond to second color value (27, 42, 0) and point 34 may correspond to second color value (25, 42, 0).
Because a sparse lookup table includes only a subset of all possible first color combinations, many first color values will map to a point within this three dimensional space that does not correspond to one of the lookup table entries. For example, point 36 in FIG. 1 depicts a first color value that does not correspond to any entry in the lookup table. Instead, point 36 is surrounded by the eight entries corresponding to points 20, 22, 24, 26, 28, 30, 32 and 34.
One conventional technique for assigning second color values to the set of first color values represented by point 36 is to interpolate between the known second color values associated with the surrounding lookup table entries. More particularly, interpolation is performed between the second color values that correspond to some or all of the eight first color values that define the surrounding cube. Examples of such commonly known interpolation techniques are trilinear (e.g., as described in Kasson et al. U.S. Pat. No. 5,390,035), tetrahedral (e.g., as described in Sakamoto et al. U.S. Pat. No. 4,275,413), cubic (e.g., as described in Murakami et al. U.S. Pat. No. 5,930,388 (“Murakami”)), prism (e.g., as described in Murakami), and other suitable interpolation techniques.
One problem with previously known interpolation techniques occurs when one of the second color values saturates at the low end (e.g., output value of 0) or high end (e.g., output value of 255) of the color value scale. An example of this “saturation error” is depicted in FIG. 2, which shows an array corresponding to a portion of a single dimension of the lookup table of FIG. 1. In particular, FIG. 2 illustrates an array having first color values at points 40, 42, 44, 46 and 48. In general, each point in the lookup table is associated with multiple second color components (e.g., three second color components such as in a CMY color space). For simplicity, only a single second color value is shown associated with each point in FIG. 2. Thus, points 40, 42, 44, 46 and 48 have associated second color values 25, 15, 5, 0 and 0, respectively.
Point 50 depicts a first color value that does not correspond to any entry in the lookup table, but instead is located halfway between points 44 and 46. Conventional linear interpolation techniques produce a second color value of ((5+0)÷2)=2.5 associated with point 50. However, this result is incorrect. In particular, assuming that the distance between second color components associated with points 42 and 44 (15−5=10 units) equals the distance between second color components associated with points 44 and 46, and assuming linearity in this region, the second color component associated with point 46 should have a value of −5. Because color component values are typically represented as unsigned numbers, however, the −5 value typically is clipped to 0. If the second color component value of point 46 were not so clipped, however, linear interpolation would produce a correct value of ((5+(−5))÷2)=0 for the second color component associated with point 50.
Although not shown in FIG. 2, the same saturation problem occurs at the other end of the color value scale. In particular, conventional linear interpolation techniques produce erroneous values when a second color component saturates at the high end of the color scale (e.g., 255 for an 8-bit color system). One consequence of the saturation-value interpolation error is that color components that should have 0 values actually contain non-zero values, and therefore look “dirty.” This effect is most apparent with a light color component (e.g., light yellow) because any contamination of the color components is readily noticeable. The effect at the high end of the color scale also produces erroneous results.
The errors described above occur regardless of the type of linear interpolation used, the number of dimensions of the lookup table, or the number of bits used to represent color component values. Thus, in a 16-bit system used to covert RGB to CMYK data, in which color components may have any value between 0 and 65,535, the same type of interpolation error occurs when any of the four second color component values saturate at the low end (i.e., 0) or the high end (i.e., 65,535) of the color scale.
In view of the foregoing, it would be desirable to provide methods and apparatus for converting a first color value to a second color value without saturation error.